package _18_剑指OfferII;

import _18_剑指OfferII.datastrcute.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class _043_剑指OfferII往完全二叉树添加节点 {

    private Queue<TreeNode> containers;

    private TreeNode root;

    public _043_剑指OfferII往完全二叉树添加节点(TreeNode root) {
        if (root == null) return;
        this.root = root;
        containers = new LinkedList<>();
        containers.offer(root);
        while (!containers.isEmpty() && containers.peek().left != null && containers.peek().right != null) {
            TreeNode node = containers.poll();
            containers.add(node.left);
            containers.add(node.right);
        }
    }

    public int insert(int v) {
        TreeNode node = new TreeNode(v);
        TreeNode parent = containers.peek();
        if (parent.left == null) {
            parent.left = node;
        } else {
            parent.right = node;
            containers.add(parent.left);
            containers.add(node);
            containers.poll();
        }
        return parent.val;
    }

    public TreeNode get_root() {
        return root;
    }


    // 二叉树性质
  /*  private List<TreeNode> containers = new ArrayList<>();

    public _043_剑指OfferII往完全二叉树添加节点(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            containers.add(node);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }

    public int insert(int v) {
        int parent = (containers.size() - 1) >> 1;
        TreeNode newNode = new TreeNode(v);
        TreeNode parentNode = containers.get(parent);
        if (parentNode.left == null) {
            parentNode.left = newNode;
        } else {
            parentNode.right = newNode;
        }
        containers.add(newNode);
        return parentNode.val;
    }

    public TreeNode get_root() {
        if (containers.isEmpty()) return null;
        return containers.get(0);
    }*/

}
